package dp.longestArithSeqLength;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @Date 2020/05/05
 * @author 王光浩 
 * @Thinking 找出以所有元素为结尾的所有等差数列的长度，然后从中找出最大长度。 			 
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n^2）
 */
public class MyMethodOne {
	public int longestArithSeqLength(int[] A) {
		if( A==null ) return -1;
		if( A.length<=1 ) return A.length;
		//存储每一个以每一个元素为结尾的所有等差数列的等差值，以及对应的最大长度
		List<HashMap<Integer,Integer>> help = new ArrayList<HashMap<Integer,Integer>>();
		int maxLen = 0;
		help.add(new HashMap<Integer,Integer>());
		//获取以 下标为 i 结尾的所有等差数列的等差值与最大长度
		for( int i = 1 ; i<A.length ; i++ ) {
			help.add(new HashMap<Integer,Integer>());
			for( int  j = 0 ; j<i ; j++ ) {
				int key = A[i]-A[j]; 
				//如果 以j 结尾的所有等差数列中包含了差值为 key 的等差数列，则获取对应的等差数列
				//长度，否则 创建一个新的等差数列，差值为 key，长度为2
				if(help.get(j).containsKey(key)) {
					int value = help.get(j).get(key)+1;
					//如果 已经计算出以 i下标元素 结尾的所有等差数列中已经包含了 等差值为 key 的等差数列
					//则将原值与 value 进行比较，获取大的
					if( help.get(i).containsKey(key) )
						help.get(i).put(key, value>help.get(i).get(key)?value:help.get(i).get(key));
					else
						help.get(i).put(key,value);
				} else {
					help.get(i).put(key,2);
				}
				maxLen = help.get(i).get(key)>maxLen ? help.get(i).get(key):maxLen;
			}
		}
		return maxLen;
    }
}
